package bintree.heap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 基于动态数组实现的最大堆
 * @author yuisama
 * @date 2022/05/16 21:30
 **/
public class MaxHeap {
    // 实际存储元素的数组
    private List<Integer> elementData;
    // 当前堆中元素个数
    private int size;

    public MaxHeap() {
        this(10);
    }

    public MaxHeap(int size) {
        elementData = new ArrayList<>(size);
    }

    /**
     * 将任意的整型数组arr调整为堆
     * @param arr
     */
    public MaxHeap(int[] arr) {
        elementData = new ArrayList<>(arr.length);
        // 1.先将所有元素复制到data数组中
        for (int i : arr) {
            elementData.add(i);
            size ++;
        }
        // 2.从最后一个非叶子结点开始进行siftDown操作
        for (int i = parent(size - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public void add(int val) {
        // 1.直接向数组末尾添加元素
        elementData.add(val);
        size ++;
        // 2.进行元素的上浮操作
        siftUp(size - 1);
    }

    /**
     * 取出当前最大堆的最大值
     * @return
     */
    public int extractMax() {
        if (size == 0) {
            throw new NoSuchElementException("heap is empty!cannot extract!");
        }
        // 树根就是最大值结点
        int max = elementData.get(0);
        // 将数组的末尾元素顶到堆顶
        elementData.set(0,elementData.get(size - 1));
        // 将数组的最后一个元素从堆中删除
        elementData.remove(size - 1);
        size --;
        // 进行元素的下沉操作，从索引为0开始
        siftDown(0);
        return max;
    }

    public int peekMax() {
        if (isEmpty()) {
            throw new NoSuchElementException("heap is empty!cannot peek!");
        }
        return elementData.get(0);
    }

    /**
     * 从索引k开始进行元素的下沉操作
     * @param k
     */
    private void siftDown(int k) {
        // 还存在子树
        while (leftChild(k) < size) {
            int j = leftChild(k);
            // 此时还存在右子树
            if (j + 1 < size && elementData.get(j + 1) > elementData.get(j)) {
                // 此时还存在右子树且右子树的值还比左子树大
                j ++;
            }
            // 索引j一定对应了左右子树的最大值索引
            if(elementData .get(k) >= elementData.get(j)) {
                // 当前元素 >= 左右子树最大值，下沉结束，元素k落在了最终位置
                break;
            }else {
                swap(k,j);
                k = j;
            }
        }
    }


    private void siftUp(int k) {
        while (k > 0 && elementData.get(k) > elementData.get(parent(k))) {
            swap(k,parent(k));
            k = parent(k);
        }
    }

    private void swap(int k, int parent) {
        int child = elementData.get(k);
        int parentVal = elementData.get(parent);
        elementData.set(k,parentVal);
        elementData.set(parent,child);
    }


    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 找到结点k对应的父节点的索引
     * @param k
     * @return
     */
    private int parent(int k) {
        return (k - 1) >> 1;
    }

    /**
     * 找到结点k对应的左子树的索引
     * @param k
     * @return
     */
    private int leftChild(int k) {
        return (k << 1) + 1;
    }

    /**
     * 找到结点k对应的右子树的索引
     * @param k
     * @return
     */
    private int rightChild(int k) {
        return (k << 1) + 2;
    }

    @Override
    public String toString() {
        return elementData.toString();
    }
}